package i.g.sbl.tree.model;

import java.util.*;
import java.util.function.BiConsumer;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;

public interface Tree<T, R extends Tree<T, R>> extends Cloneable {
    T getRoot();

    Deque<R> getChildren();

    /**
     * 从当前节点中序遍历
     *
     * @param consumer
     */
    default void travelFromRoot(Consumer<R> consumer) {
        Stack<R> stack = new Stack<>();
        stack.push(typed());
        while (!stack.isEmpty()) {
            R item = stack.pop();
            consumer.accept(item);
            if (item.getChildren() != null) {
                Iterator<R> rIterator = item.getChildren().descendingIterator();
                while (rIterator.hasNext()) {
                    stack.push(rIterator.next());
                }
            }
        }
    }

    /**
     * 从当前节点中序遍历
     *
     * @param consumer，支持同时消费当前节点的父节点和当前节点
     */
    default void travelFromRoot(BiConsumer<Optional<R>, R> consumer) {
        Stack<Pair<Optional<R>, R>> stack = new Stack<>();
        stack.push(new Pair<>(Optional.empty(), typed()));
        while (!stack.isEmpty()) {
            Pair<Optional<R>, R> item = stack.pop();
            R curNode = item.getRight();
            consumer.accept(item.getLeft(), curNode);

            if (curNode.getChildren() != null) {
                Iterator<R> rIterator = curNode.getChildren().descendingIterator();
                while (rIterator.hasNext()) {
                    stack.push(new Pair<>(Optional.of(curNode), rIterator.next()));
                }
            }
        }
    }


    /**
     * 从当前节点后序遍历
     *
     * @param consumer
     */
    default void travelFromEnd(Consumer<R> consumer) {
        Stack<R> stack = new Stack<>();
        stack.push(typed());
        while (!stack.isEmpty()) {
            R peek = stack.peek();
            if (peek != null) {
                stack.push(null);
                if (peek.getChildren() != null) {
                    stack.addAll(peek.getChildren());
                }
            } else {
                stack.pop();    // 弹出null
                R item = stack.pop();
                consumer.accept(item);
            }
        }
    }

    /**
     * 用真实类型返回实例自身
     *
     * @return
     */
    default R typed() {
        return (R) this;
    }

    /**
     * 获取最大深度
     *
     * @return
     */
    default int getDepth() {
        int depth = 1;
        for (R child : getChildren()) {
            depth = Math.max(child.getDepth() + 1, depth);
        }
        return depth;
    }

    /**
     * 获取所有的叶子节点。如果当前节点没有子节点，则也作为叶子节点返回
     *
     * @return
     */
    default List<R> getLeafs() {
        List<R> leafs = new LinkedList<>();
        travelFromRoot(item -> {
            if (item.getChildren().isEmpty()) {
                leafs.add(item);
            }
        });
        return leafs;
    }

    /**
     * 将所有的层级关系转换成Map结构，key为父节点，value为其子节点列表
     *
     * @return
     */
    default Map<R, Set<R>> toMap() {
        Map<R, Set<R>> map = new HashMap<>();
        travelFromRoot((parent, cur) -> {
            if (parent.isPresent()) {
                Set<R> children = map.computeIfAbsent(parent.get(), p -> new HashSet<>());
                children.add(cur);
            }
        });
        return map;
    }

    /**
     * 层序遍历
     * @param consumer
     */
    default void travelLevel(Consumer<R> consumer) {
        Queue<R> queue = new LinkedList<>();
        queue.add(typed());

        while (!queue.isEmpty()) {
            R item = queue.poll();
            consumer.accept(item);

            if (item.getChildren() != null) {
                queue.addAll(item.getChildren());
            }
        }
    }

    /**
     * 从根节点遍历，裁剪分支
     * @param predicate
     * @return  条件为true的分支留下
     */
    Optional<R> filter(Predicate<R> predicate);

    /**
     * 从根节点遍历，并替换当前节点
     *
     * <p>由于从根节点遍历，所以map方法返回的节点并不是最终结果的节点，因为会对子节点重构后，再重新组装成一个新的节点</p>
     * @param function
     * @return
     */
    <I, O extends Tree<I, O>> O map(Function<R, O> function);

    <I, O extends Tree<I, O>> O mapItem(Function<T, I> function);

    Optional<R> findFirst(Predicate<R> predicate);
}
